//155. 最小栈
//思路：准备两个栈，一个栈正常进数据，另一个栈先进第一个数据
//后面比较val与_minst.top，如果val <= _minst.top()就进栈
//等于的时候也需要进栈，因为如果出栈的话可能会导致最小值被漏出掉



#include <stack>
using namespace std;

class MinStack {
public:
    MinStack() {
    }
    
    void push(int val) {
        _st.push(val);
        if(_minst.empty() || val <= _minst.top())
        {
            _minst.push(val);
        }
    }
    
    void pop() {
        if(_st.top() == _minst.top())
        {
            _minst.pop();
        }
        _st.pop();
    }
    
    int top() {
        return _st.top();
    }
    
    int getMin() {
        return _minst.top();
    }

    stack<int> _st;
    stack<int> _minst;
};
